public class Test {
    public static void main1(String[] args) {
        String s = "PAYPALISHIRING";
        s = convert(s,3);
        StringBuilder stringBuilder = new StringBuilder();
    }
    //Z字型
    public static String convert(String s, int numRows) {
        if(numRows == 1) return s;
        int len = s.length();
        char[] str = new char[len];
        int d = numRows*2-2,k=0;//计算公差
        //1.读入第一行
        for(int i=0;i<len;i=i+d) str[k++] = s.charAt(i);
        //2.读入中间行
        for(int i=1;i<numRows-1;i++) {//控制行
            int x=1,y=d-i;
            while (true) {
                if(x<len)
                    str[k++] = s.charAt(x);
                else break;
                if(y<len) {
                    str[k++] = s.charAt(y);
                }else break;
                x+=d;
                y+=d;
            }
        }
        //3.读入最后一行
        for(int i=numRows-1;i<len;i=i+d)
            str[k++] = s.charAt(i);
        return String.valueOf(str);

    }

    public static void main(String[] args) {
        String s = "10";
        numDecodings(s);
    }
    //91.解码
    public static int numDecodings(String s) {
        int n = s.length();
        //1.定义dp,dp[i]表示0-i位置字符串的总解码方法
        int[] dp = new int[n];
        int i = 0;//遍历字符串
        //2.初始化dp[0]
        if(s.charAt(i) != '0') dp[i++]=1;
            //优化1：第一个数为0的字符串无法解码
        else return 0;
        //2.初始化dp[1]
        if(n>1) {
            if(s.charAt(i-1)>='3'&&s.charAt(i) =='0') {
                dp[1] = 0;
            }else if(s.charAt(i-1)=='1' && s.charAt(i) >='1' || s.charAt(i-1)=='2'&&s.charAt(i)>='1'&&s.charAt(i)<='6') {
                dp[1]=2;
            }else {
                dp[1]=1;
            }
        }
        i++;
        //优化2：最后一个字符是0且倒数第二个字符大于2，整个串不能完成解码
        if(n>2 && s.charAt(n-2)>'2'&&s.charAt(n-1)=='0') return 0;
        //3.从第三个字符开始填表，i=3
        while(i<n) {
            char ch = s.charAt(i);
            int x=0,y=0;
            if(ch != '0') x = dp[i-1];
            char ch2 = s.charAt(i-1);
            if(ch2 == '1' || ch2 == '2' && ch <= '6') y = dp[i-2];
            dp[i++] = x+y;
        }
        //4.返回值
        return dp[n-1];
    }

}
